\section{Fundamentação Teórica}
\label{sec:fundamentacao}

Para realizar a predição de disponibilidade, um sistema deve levar em conta o histórico de uma máquina buscando inferir o estado futuro. Plummer~\cite{Plummer2000} estuda o uso da predição em séries temporais através do uso de redes neurais. O autor ainda faz uso da técnica de \textit{K-nearest neighbor}, desenvolvida por Cover e Hart~\cite{Cover1967}, como base de comparação. Neste trabalho serão usadas 5 técnicas de classificação: \textit{K-nearest neighbor}, redes bayesianas, árvore de decisão, redes neurais e uma técnica de predição simples.

Para realizar a predição, Plummer primeiramente trabalhou modelando a base de dados a ser explorada. A idéia, é ser capaz de inferir o efeito do histórico de disponibilidade analisando o peso dos estados de tempos passados. Considerando que deseja-se prever o tempo $T_n$: busca-se inferir o peso do valor de disponibilidade dos tempos $T_{0}$, ..., $T_{n-3}$, $T_{n-2}$, $T_{n-1}$ no cálculo da disponibilidade em $T_n$.

\subsection{Entrada do Sistema}
\label{entrada}

%T_ODO Não seria até $T_{n-M}$? Caso contrário, com uma janela de tamanho M=1, eu usuaria o próprio T_n para prever T_n!? NÃO FAZ O MENOR SENTIDO USAR M = 1!!!!!
Analisar todo o histórico para o cálculo de uma predição não é eficiente para o modelo de disponibilidade. Em geral, devem ser avaliados os tempos passados que são significativos para o tempo futuro, de maneira que a técnica de predição utilizada não trabalhe com ruído ou com uma grande quantidade de dados. A decisão do tamanho da janela é algo dependente do domínio da aplicação. Assim, uma janela de tamanho $M$ (com $M > 1$) seria composta pelos seguintes instantes de tempo: $T_{n-(M-1)}$, ..., $T_{n-2}$, $T_{n-1}$, $T_n$. Neste caso, os instantes $T_{n-(M-1)}$, ..., $T_{n-2}$, $T_{n-1}$ são usados para predizer $T_n$.

Dado um histórico de disponibilidade, a primeira janela de tamanho $M$ é criada a partir do tempo $0$. Movendo esta janela em uma unidade de tempo, cria-se uma nova janela de tamanho $M$ que começa no tempo $1$. Esta etapa é feita sucessivamente até que a última janela tenha todos os últimos estados do histórico. Assim, para $M = 2$, por exemplo, e para um histórico de 4 unidades de tempo, existem 3 possíveis janelas a serem utilizadas como entrada de cada técnica: $(T_0, T_1)$, $(T_1, T_2)$ e $(T_2, T_3)$.

\subsection{Metodologia de Treinamento}

%T_ODO Apenas uma observação, achei que a Metodologia ficou com cara de Fundamantação teórica.  OK

Cada uma das técnicas a serem exploradas passam por dois processos: treinamento e validação. Durante o treinamento, a técnica conhece a entrada e a saída esperada, de forma que é capaz de se ajustar para satisfazer a saída indicada. Já na validação, a técnica recebe uma entrada e precisa ser capaz de prever a saída. Caso a saída obtida da técnica seja diferente daquela apontada na base de dados, houve um erro na predição realizada pela técnica.

%T_ODO WARNING! Copy & Paste detected :-)
% "...proporcao de cada uma das letras...". Isto é um exemplo no contexto do projeto2, mas não no projeto final DONE
Para que a técnica não se vicie numa determinada base de dados, é adequado que a base de dados utilizada para treinamento seja distinta daquela usada para testes. Para tanto, uma boa estratégia é dividir toda a base de dados conhecida em duas: uma com as instâncias utilizadas para teste e outra com as instâncias utilizadas para treinamento. Esta divisão deve buscar também manter a representatividade de cada valor a ser obtido na saída. Por exemplo, deve-se tentar obter a mesma proporção de disponibilidade nas janelas de estados tanto na base de treinamento como na de testes.

Kohavi~\cite{Kohavi1995} analisa três técnicas possíveis de serem usadas no processo de validação, incluindo a validação cruzada (\textit{k-fold}), técnica adotada neste trabalho. Nela, a base de dados é particionada em $k$ novas base de dados. Então, $1$ parte é escolhida como base de teste e as outras $k - 1$ partes escolhidas como base de treinamento. Este processo é repetido $k$ vezes: cada vez selecionando uma parte diferente para ser tomada como base de testes. Kohavi discute como um valor pequeno de $k$ pode aumentar a variância, enquanto um valor alto pode incentivar um viés (especialização na base de treinamento) da técnica analisada. O autor ainda discute a importância de manter a proporção dos elementos em ambas as bases de treinamento e de teste, e cita que a melhor análise e comparação entre duas técnicas validadas se dá pela múltipla execução da técnica com bases de dados de diferentes particionamentos.

Neste trabalho, será utilizada a validação cruzada \textit{10-fold} para a comparação dos melhores resultados obtidos de cada uma das técnicas.

\subsection{Descrição das Técnicas de Predição}

Cada uma das técnicas de predição apresentada utiliza uma fundamentação teórica distinta para inferir sobre padrões na base de treinamento. Nesta subseção, discute-se a base teórica que fundamenta cada técnica, explicando os parâmetros e simplificações consideradas neste trabalho.

\subsubsection{k-Nearest Neighbor}

A técnica \textit{k-Nearest neighbor}  faz uso de uma estratégia simples porém poderosa: dada $N$ entradas de treinamento, ao efetuar um teste de uma instância $i$ para realizar a predição, esta técnica irá procurar quais são as $k$ instâncias da base de treinamento que são mais parecidas com $i$. Analisando a predição esperada das $k$ entradas, infere-se a saída de $i$.

\subsubsection{Redes Bayesianas}

A rede bayesiana segue os princípios de probabilidade condicional. A partir da análise de cada valor de disponibilidade na entrada, a rede avalia a probabilidade que cada atributo influencia na saída esperada. Assim, durante a etapa de teste, cada valor de disponibilidade tem um impacto probabilístico sobre a predição a ser realizada.

John e Langley~\cite{John1995} discutem a implementação de uma rede bayesiana simples que será usada neste trabalho. Nela não são considerados eventuais relacionamentos entre os estados de disponibilidade no tempo (ou seja, são eventos independentes), nem considera a existência de atributos ocultos interferindo no resultado da predição.

\subsubsection{Árvores de Decisão}

Uma árvore de decisão busca estabelecer um relacionamento entre as ocorrências dos valores de disponibilidade. Inicialmente, a árvore de decisão identifica o instante de tempo mais relevante para prever a disponibilidade e coloca-o no nó raiz. Este nó então divide-se em cada um dos valores possíveis do atributo (disponível e indisponível). Após isso, é identificado então o segundo atributo mais relevante, dado cada possível valor do atributo anterior. Este novo atributo compõe um novo nó filho que será novamente subdividido. Este processo se repete até que não haja mais atributos a serem considerados. Construída a árvore, cada folha contém um valor (disponível ou indisponível) indicando o estado do tempo a ser previsto.

%T_ODO No exemplo mostrado, o resultado para $T_2$ só depende do valor de $T_1$. Mesmo assim, a árvore gerada
%pelo J48 seria essa mostrada na figura mesmo? - Sim, só não seria em caso de poda.
%T_ODO O instante de tempo T_n a ser predito é contabilizado no tamanho da janela? Ex: Para M=2, quero descobrir o instante T_n. Me utilizo dos instantes T_(n-1) e T_(n-2) ou uso apenas T_(n-1)? Se devo utilizar os dois instantes, então o exemplo abaixo é de uma janela com 2 unidades de tempo, e não 3. N é o último valor da janela. Vc vai prever T_2. . . 
A página Monk Tutorial~\cite{Monk2009} descreve a árvore de decisão J48, técnica também utilizada neste trabalho. Um exemplo da árvore de decisão de uma base de dados com janela de 3 unidades de tempo é exibido na Figura~\ref{fig:dt}. É possível observar que $T_1$ é a medida mais relevante para o cálculo de $T_2$, com valores representados nas folhas da árvore.

\begin{figure}[h!]
  \centering
  \includegraphics[scale=0.4, bb=0 0 300 220]{./images/dt.png}
  \caption{Árvore de Decisão}
  \label{fig:dt}
\end{figure}

\subsubsection{Redes Neurais}

%T_ODO ops, no parágrafo seguinte  você ainda está falando de Caracteres e imagem, contextualiza em Diponibilidade OK

Uma rede neural artificial é uma técnica análoga às redes neurais biológicas, em que um conjunto de neurônios recebem um estímulo e, ao se comunicar com outros neurônios, produzem uma determinada saída. Cada neurônio tem um peso característico, bem como uma função de ativação que determina a saída do neurônio, dada suas entradas. Assim, pode-se aplicar a técnica ao desafio de predição de disponibilidade considerando que há um neurônio para cada valor da série temporal analisada, sendo a saída o resultado da predição para o próximo instante de tempo.

Este trabalho aborda o modelo de rede neural multi-camada Perceptron. Neste modelo, a rede neural é composta de uma camada de entrada, uma camada de saída e uma ou mais camadas intermediárias. Cada camada contém um número específico de neurônios, como exemplo, na Figura~\ref{fig:nn}, a rede dispõe de 7 neurônios na camada de entrada, 3 na camada intermediária e 1 na camada de saída. Devido a esta distribuição, esta rede também é conhecida como rede neural 7-3-1.

\begin{figure}[h!]
  \centering
  \includegraphics[scale=0.4, bb=0 0 428 352]{./images/neural_network.png}
  % neural_network.png: 428x352 pixel, 72dpi, 15.10x12.42 cm, bb=0 0 428 352
  \caption{Rede Neural 7-3-1}
  \label{fig:nn}
\end{figure}

%T_ODO O valor $M$ estava sendo usado até então para representar a quantidade de instantes de tempos anteriores
%ao que se deseja ser previsto que serão usados para predição. Agora, ao se falar em $M - 1$ neurônios de 
%entrada dá a impressão que ele não representa mais a mesma coisa. - DONE!
%T_ODO Acho que a correção do tODO acima alterando os outros lugares onde se falava em $M$, e não alterando
%o valor de $M - 1$ abaixo acabou introduzindo o bug de que pra descobrir $T_n$ com uma janela de M=1 eu
%acabo usando o próprio $T_n$. Sugestão: Mudar de $M - 1$ para $M$ neste parágrafo e deixar o $M$ como 
%estava antes nos parágrafos anteriores. -- NAO FAZ SENTIDO USAR M = 1 NAO FAZ! ZERO NOTHING NADA NIET NONE NIL.
Para modelar uma rede neural é preciso identificar as entradas e saídas desta rede neural. Considerando o modelo de predição de disponibilidade, uma rede neural precisa ter $M - 1$ neurônios de entrada (1 para cada unidade de tempo, menos último tempo, que irá ser previsto), e 1 neurônio de saída (o tempo a ser previsto). Assim, ao alimentar a rede neural com uma determinada entrada, a rede neural retorna, para cada série temporal de disponibilidade, o estado esperado da máquina no próximo instante de tempo. Determinar o número de nós na camada intermediária não é algo preciso e será discutido mais adiante.

%T_ODO WARNING! Copy & Paste detected :-)
%"...imagem de uma letra conhecida..." - done
A rede neural precisa primeiro determinar como cada neurônio reage a um estímulo. Isto ocorre através de duas medidas: a taxa de aprendizagem e o momentum. Durante a etapa de treinamento, a rede neural recebe como estímulo uma janela de estados conhecida. A rede neural analisa então cada neurônio de saída identificando aqueles que cometeram um erro de predição e os pesos dos neurônios de saída são corrigidos. Em seguida, esta diferença de erro é propagada para as camadas anteriores, onde os neurônios, a partir desta diferença, tentam corrigir o peso que deram a determinado estímulo. Esta correção é proporcional à taxa de treinamento (quanto mais alto, maior diferença do novo peso para o peso antigo).

De acordo com Orr~\cite{Orr1999},  momentum é um acréscimo a esta estratégia: além da variação ocasionada pela taxa de treinamento, adiciona-se ao peso a última variação do peso do neurônio multiplicado pelo momentum. A idéia disso é de que como o peso é alterado pela taxa de aprendizado, este termo adicionado impede que haja um deslocamento maior do que a medida necessária. O momentum também permite a convergência, na medida de que a variação da correção do peso tenderia a diminuir numa rede neural convergente.

Considerando esta fundamentação teórica, serão discutidos três parâmetros ajustáveis numa rede neural: o número máximo de iterações, a taxa de aprendizado e o número de nós na camada intermediária.

\textbf{Quantidade máxima de iterações}

Dada uma base de treinamento da rede neural, é possível passar várias vezes pela mesma base de treinamento buscando adaptar os pesos dos neurônios para se adequar as entradas fornecidas. Entretanto, cada passagem representa um custo de processamento associado em que, não necessariamente, processar as entradas repetitivamente ou até mesmo processar todas as entradas implica em melhorar significativamente a rede. Skapura~\cite{Skapura1995} discute esta relação.

Para uma base em que os dados estejam bem distribuídos e que os atributos a serem analisados não apresentam valores divergentes dentro de cada classe que se deseja obter na saída, não há vantagem em usar um número de iterações maior do que a medida da própria base de treinamento. No entanto, um valor pequeno não é suficiente para obter um bom treinamento.

Em geral, o número de iterações é uma medida que serve como limite superior, as redes neurais também podem fazer uso do erro geral obtido como medida para parar o treinamento. Por exemplo, poderia-se parar o treinamento quando o erro geral fosse de 5\%.

\textbf{Taxa de aprendizado}

A variação da taxa de aprendizado é outra medida a ser considerada durante o treinamento de uma rede neural, e seu significado já foi discutido anteriormente. Entretanto, a taxa de aprendizado relaciona-se diretamente com a medida de momentum, como apresenta Orr~\cite{Orr1999}. Como o momentum vai adicionar o fator de variação entre o peso atual e o peso anterior, uma elevada taxa de aprendizado com um alto valor de momentum pode fazer com que a rede neural divirja: a variação torna-se excessiva, impedindo a convergência.

%T_ODO "... uma baixa convergência ..." !?
No entanto, uma baixa taxa de aprendizado pode ocasionar uma baixa convergência, implicando na necessidade de mais iterações. Assim, o número de iterações e o momentum devem ser considerados ao definir o valor da taxa de aprendizado.
  
\textbf{Quantidade de neurônios intermediários da rede}

Um dos parâmetros mais complexos de se estimar e explorar numa rede neural é o número de nós intermediários numa rede. Grande fonte desta dificuldade está no fato de que a literatura apresenta diversas sugestões de um valor inicial apropriado para o número de nós intermediários. Uma compilação de valores iniciais sugeridos pode ser encontrada na Internet~\cite{Faq2009}:
    \begin{itemize}
      \item Um valor entre o número de nós na camada de entrada e o número de nós na camada de saída;
      \item A soma do número de nós na entrada e número de nós de saída multiplicado por $2/3$;
      \item Um valor menor que o número de nós na camada de entrada;
      \item Um valor menor do que o dobro do número de nós na camada de entrada;
      \item Igual a quantidade de componentes (atributos e relacionamentos) que capturem boa parte do conjunto de validação.
    \end{itemize}

Dieterle~\cite{Dieterle2003} apresenta outro aspecto do número de nós na camada intermediária: um elevado número de nós pode ocasionar uma especialização nos dados de treinamento, o que significa que a rede neural não é capaz de generalizar para os casos fora da base de treinamento. Assim, uma medida muito alta pode diminuir a qualidade da rede neural.

\subsection{Predição Simples}

A técnica de predição simples serve como base para determinar se alguma técnica conseguiu realizar uma predição mais complexa do instante $T_n$ sem ser observando apenas $T_{n-1}$. Basicamente, é prevista que a disponibilidade em $T_n$ seja igual a $T_{n-1}$. Caso as demais técnicas não consigam obter uma predição melhor do que esta, significa que o sistema está apenas inferindo a regra de que ``uma máquina tende a manter seu último estado'' independente do histórico de disponibilidade.

\section{Metodologia}
\label{sec:metodologia}
Nesta seção será descrita a metodologia usada na construção dos experimentos para análise do comportamento das diferentes técnicas na predição de disponibilidade. Primeiramente discute-se a geração da base de dados que será usada como entrada e, em seguida, os cenários de execução dos experimentos.

\subsection{Base de Dados}

Foram capturadas as estatísticas de acesso e disponibilidade do Laboratório de Ciência da Computação da Universidade Federal de Campina Grande. As estatísticas de acesso correspondem ao período do dia 10 de Agosto até o dia 4 de Setembro de 2009. O laboratório apresentou $32$ máquinas com o sistema operacional GNU/Linux durante o período de coleta. A informação de disponibilidade é extraída a partir dos arquivos de informações gerais do sistema: \textit{/var/log/messages} e de acesso de segurança: \textit{/var/log/auth.log}. Do primeiro arquivo são extraídas as informações sobre quando a máquina está ligada ou desligada. Do segundo arquivo obtém-se informações de quando os usuários acessam a máquina.

Kondo~\cite{Kondo2005} discute as melhores métricas e práticas a serem realizadas durante a construção de estatísticas de disponibilidade. Em especial, o autor caracteriza a disponibilidade em três níveis: disponibilidade da máquina, disponibilidade de execução e disponibilidade do processador. Apesar de tais medidas serem importantes para simular uma grade oportunista, para o foco deste trabalho será considerada apenas a disponibilidade de execução, isto é, quando a máquina pode executar algo originado da grade. Se a máquina estiver com um usuário ou se ela estiver desligada, a máquina é considerada indisponível para execução. Do contrário, a máquina é considerada disponível para execução. A disponibilidade da CPU, ou o quanto a CPU está disponível a cada intervalo de tempo, é desconsiderada: o processador das máquinas do laboratório são tipicamente utilizadas apenas pelos usuários, e tal informação não é relevante para a predição da disponibilidade de execução.

Cada um dos arquivos de \textit{log} são processados para gerarem uma base de dados intermediária. Esta base de dados intermediária é descrita por linhas que representam o tempo relativo de um evento (onde zero é o tempo inicial de captura do \textit{log} em minutos) e o evento associado. O Exemplo~\ref{lst:bd_inter} mostra parte deste arquivo, onde $1$, $2$, $3$ e $4$ representam os eventos de: máquina ligada, usuário utilizando a máquina, usuário saiu da máquina e máquina desligada.

\begin{lstlisting}[caption={Arquivo intermediário dos dados de disponibilidade}, label={lst:bd_inter}]
3855 1
3857 2
3870 3
3874 2
3904 3
3907 4
\end{lstlisting}

%T_ODO Em nenhum momento é explicado o que é uma "...janela do evento..." - DONE
Seguindo a modelagem feita por Plummer~\cite{Plummer2000}, a partir desta informação é extraído o arquivo final que armazena os dados a serem processados. Este trabalho faz uso do formato \textit{ARFF} utilizado pelo Weka~\cite{Weka2005}. Cada arquivo contém em cada linha, na parte de dados, $N$ números $0$ ou $1$ representando indisponibilidade ou disponibilidade da máquina. $N$ é obtido a partir do tamanho da janela de predição sobre o a unidade de tempo de cada estado. Ou seja, ao utilizar uma unidade de tempo de 60 minutos por estado com uma janela de predição de 2 dias, $N = 48$. As janelas foram extraídas como discutido na subseção~\ref{entrada}.

%T_ODO Alguma referência para o que é dito na última frase? Só por completude mesmo... Nops
Para que as técnicas de predição pudessem trabalhar de maneira inequívoca, foram apenas inseridos na base de dados final estímulos únicos. Ou seja: não há duas janelas que apresentem o mesmo valor de disponibilidade em todos os tempos. É importante utilizar de estímulos únicos, pois a repetição pode gerar um viés aos padrões que se repetem no lugar de gerar uma predição única para cada padrão.

Para validar a capacidade de predição do simulador, foi criada uma base de dados artificial, onde a indisponibilidade ocorria nos tempos múltiplos de 4 ou 7. A partir disso foram criadas todas as janelas possíveis para tais dados artificiais no formato de dados \textit{ARFF}.

\subsection{Cenários}

%T_ODO Falta a referência para a informação de uma hora de duração das tarefas - Ignorado, não tenho.
Para a realização do experimento, cada máquina teve um estado de disponibilidade na janela de estados representando 60 minutos. Se durante um período de 1 hora, a máquina ficou algum instante indisponível, ela é considerada no estado indisponível. A escolha de uma hora é uma medida padrão adotada pelos trabalhos na área, como os apresentados na Seção~\ref{sec:relacionados}.

Cada janela de estados teve o tamanho definido em dois dias ($M = 48$). A escolha por dois dias de histórico em cada janela deve-se ao padrão de uso do laboratório. Durante a segunda e quarta-feira, o laboratório tem $6$ horas de aula. Na quinta, $4$ horas de aula, na sexta $2$ horas, ficando a terça-feira inteira livre. Ainda, os usuários podem usar livremente o laboratório das 07:00 às 22:00, mas acredita-se que os horários de aula representem o maior período de indisponibilidade das máquinas. Assim, os padrões de uso de pelo menos dois dias da semana poderá ajudar na inferência do dia seguinte.

Cada histórico de disponibilidade apresenta estímulos únicos, assim, o número de instâncias a serem avaliadas varia de acordo com a máquina.

Para a escolha da rede neural, foram utilizados parâmetros conservadores: 500 iterações, 48 nós intermediários e taxa de aprendizado 0.3 com momentum 0.2. Uma abordagem mais completa na avaliação da rede neural incluiria uma varredura dos possíveis valores para estes parâmetros.

Assim, serão executados ao todo 165 cenários: o uso das 5 técnicas para cada uma das 32 máquinas e para a base de dados artificial. Procura-se realizar quantas execuções forem necessárias de cada cenário de modo que se obtenha um erro inferior a 5\% com 95\% de confiança. Para a avaliação de cada cenário utilizou-se o framework Weka~\cite{Weka2005}. O Weka apresenta uma coleção de ferramentas de mineração de dados. Implementada na linguagem Java~\cite{Java2009}, o Weka disponibiliza uma GUI e UI como interface do usuário e uma API para executar as atividades de mineração de dados a partir de outra aplicação Java.

Para a execução dos cenários, construiu-se uma aplicação a ser executada por linha de comando que faz uso da API do Weka. O programa recebe a base de dados e a técnica a ser utilizada. Como saída, são retornados o número de acertos e erros na classificação da base de teste, com o uso de validação cruzada \textit{10-fold}.
